from McTree import *
from time import clock
from math import sqrt
import sys

book = 'walrus-and-carpenter.txt'
f = open(book)
string = f.read()
f.close()
#string = 'Mississippi'

start = clock()
tree = McTree(string)
buildingtime = clock()-start

nodeDepth = dict()
stringDepth = dict()

def addToCount(counter, depth, degrees):
	if not depth in counter:
		counter[depth] = list()
	counter[depth].append(degrees)

def countDegrees(node, nodeDepthCounter):
	global nodeDepth, stringDepth
	if isinstance(node, InnerNode):
		addToCount(nodeDepth, nodeDepthCounter, len(node))
		addToCount(stringDepth, node.strDepth, len(node))
		for n in node.edges.itervalues():
			countDegrees(n, nodeDepthCounter+1)


def average(lst):
	return float(sum(lst))/len(lst)

def stddev(lst):
	my = average(lst)
	sq = sum([(x-my)**2 for x in lst])
	return sqrt(sq/len(lst))

start = clock()
countDegrees(tree.root, 0)
counttime = clock() - start

# For outputting

if 'book' in dir():
	name = 'file '+book
else:
	name = 'string '+string

depthwidth = 4
avgwidth = 13
stdwidth = 7
nowidth = 12
totalwidth = depthwidth+avgwidth+stdwidth+nowidth+4*2

def printdepths(depthlist):
	global depthwidth, avgwidth, stdwidth, nowidth
	keys = depthlist.keys()
	keys.sort()
	for d in keys:
		#print str(d).rjust(depthwidth),
		values = depthlist[d]
		#print str(len(values)).rjust(nowidth)
		avg = average(values)
		std = stddev(values)
		print '%*d  %*d  %*.3f  %*.3f' %(depthwidth, d, nowidth, len(values), avgwidth, avg, stdwidth, std)
	print
	
print "Summary over", name
print '='*totalwidth
print "Time for building tree: %5d ms" %(buildingtime*1000)
print "Time for counting: %5d ms" %(counttime*1000)

print '-'*totalwidth
print 'Depth:'.ljust(depthwidth+1),"No. of nodes:".rjust(nowidth+1),'Average count:'.rjust(avgwidth+1),'Std.dev:'.rjust(stdwidth+1)
print '-'*totalwidth

print 'By node depth:'
print '--------------'
printdepths(nodeDepth)

print 'By string depth:'
print '----------------'
printdepths(stringDepth)
